# 回路计数(好题,状态压缩DP)
import math


def path_count(num):
    """回溯法求解
    使用回溯法求解哈密顿回路(Hamiltonian Cycle)的时间复杂度是O(n!)
    当n=21时, 21! = 51,090,942,171,709,440,000, 约为 10^20 显然在考试时间内不可能完成
    实际上哈密顿回路是一个NP-Complete问题
    """
    paths = []
    cnt = 0

    def dfs(path, path_set, curr):
        nonlocal cnt, paths
        if len(path) > num:
            return
        if len(path) == num and path[-1] == 1:  # 如果访问了所有的楼, 并且最后回到1号楼
            if path not in paths:
                cnt += 1
                paths.append(path[:])

        for i in range(1, num + 1):
            if i == 1 and len(path) != num - 1:
                continue
            if i != curr and i not in path_set and math.gcd(i, curr) == 1:  # 如果两个数字互质则可以通行
                path.append(i)
                path_set.add(i)
                dfs(path, path_set, i)
                path.pop()
                path_set.remove(i)

    dfs([], set(), 1)
    print(paths)
    return cnt


def count_hamiltonian_cycles(n):
    """使用状态压缩DP的方法
    利用位掩码记录访问状态，避免路径存储，时间复杂度优化为 O(n^2 * 2^n)
    使用一个n位的二进制位数表示教学楼的访问状态, 如掩码mask=0b101时, 表示访问过1号和3号
    在哈密尔顿回路问题中，不同的路径可能到达相同的中间状态。例如：
    路径 1→2→3→5 和 1→3→2→5 都到达了相同的状态：访问过节点1、2、3、5，且当前在节点5。
    暴力DFS会分别探索这两种路径的后续可能性，导致重复计算后续的路径。
    状态压缩DP通过记录状态（如 mask=0b10111，当前节点=5），直接复用之前的结果，避免重复计算。
    例如, 如果仍有4,6两个个节点没有访问, 那么DFS要计算1→2→3→5→6(死路),1→2→3→5→4→6, 1→3→2→5→6(死路),1→3→2→5→4→6, 来分别结算
    而状态压缩DP只需要使用dp[0b10111][5]=2, 来加上后续遍历的结果就可以了
    这实际上是一种记忆搜索的方式, 即通过记忆来避免重复的搜索
    下面将记录一个n=5的情况:
    初始化:
        dp[0b00001][1] = 1（从1号节点开始）。
    mask=0b1, 从1号节点移动到相邻节点2、3、4、5：
        dp[0b00011][2] = 1
        dp[0b00101][3] = 1
        dp[0b01001][4] = 1
        dp[0b10001][5] = 1
    mask=0b10, 不存在, 因为1号节点已经访问过.
    mask=0b11, 从2号节点移动到相邻的3、5号节点：
        dp[0b00111][3] = 1
        dp[0b10011][5] = 1

    """
    # 构建图的邻接矩阵
    graph = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if math.gcd(i, j) == 1:
                graph[i][j] = 1
                graph[j][i] = 1

    # dp[mask][i] 表示已经访问过的楼的集合为 mask，并且当前在楼 i 的方案数
    dp = [[0] * (n + 1) for _ in range(1 << n)]
    dp[1][1] = 1  # 起点在楼 1，初始状态为 1 (二进制 000...001)

    # 状压DP，遍历所有状态
    for mask in range(1 << n):  # bin(mask)=0b101时, 表示访问过1号和3号; bin(mask)=0b1001时, 表示访问过1号和4号
        for i in range(1, n + 1):
            if dp[mask][i]:  # 如果当前状态 mask 下，已经到达楼 i
                for j in range(1, n + 1):  # 判断从i是否可以到达j
                    if not (mask & (1 << (j - 1))) and graph[i][j]:  # 如果楼 j 尚未访问，并且楼 i 和楼 j 之间有走廊
                        next_mask = mask | (1 << (j - 1))
                        dp[next_mask][j] += dp[mask][i]

    # 统计所有从楼 1 出发，经过所有楼并返回楼 1 的方案数
    full_mask = (1 << n) - 1  # 所有楼都被访问的状态
    result = 0
    for i in range(1, n + 1):
        if graph[i][1] and dp[full_mask][i]:  # 楼 j 和楼 1 之间有走廊，并且 dp[full_mask][j] 不为 0
            result += dp[full_mask][i]

    return result


if __name__ == '__main__':
    # print(path_count(5))
    print("不同的访问方案数量是：", count_hamiltonian_cycles(21))
